Partition List

LeetCode 86 | Difficulty: Medium

Medium

Problem Description

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example 1:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

Constraints:

- The number of nodes in the list is in the range `[0, 200]`.

- `-100 <= Node.val <= 100`

- `-200 <= x <= 200`

Topics: Linked List, Two Pointers

---

Approach

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 162 ms)

Metric	Value
Runtime	162 ms
Memory	N/A
Date	2017-10-07

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode Partition(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        ListNode dummy1 = new ListNode(Int32.MinValue);
        ListNode tail1 = dummy1;
        ListNode dummy2 = new ListNode(Int32.MinValue);
        ListNode tail2 = dummy2;

        while (head != null)
        {
            if (head.val < x)
            {
                tail1.next = head;
                head = head.next;
                tail1 = tail1.next;
                tail1.next = null;
            }
            else
            {
                tail2.next = head;
                head = head.next;
                tail2 = tail2.next;
                tail2.next = null;
            }
        }
        tail1.next = dummy2.next;
        return dummy1.next; 
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.